//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
//
// 
//
// 注意： 
//
// 
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 示例 3: 
//
// 
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 105 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 
// 👍 1371 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func minWindow(s string, t string) string {

    // tips : 滑动窗口需要同时存在需求 和 窗口两个容器！

    need, window := make(map[byte]int), make(map[byte]int) // 需求字符映射 和 已有字符映射
    matchNum := 0  // 符合条件的字符数

    res := "" // 结果

    for _, v := range []byte(t) {
        need[v]++
    }

    left, right := 0, 0  // 快慢指针

    for right < len(s) { // [s, f) 右闭区间
        v1 := s[right]
        right++

        if _, ok := need[v1]; ok {  // 满足条件 确认数+1
            window[v1]++

            if need[v1] == window[v1] {
                matchNum++
            }
        }

        // 确认最小答案 并持续缩小窗口
        for matchNum == len(need) {  // 满足完整条件 比对答案
            tmp := s[left: right]

            if res == "" || len(res) > len(tmp) {
                res = tmp
            }

            // 缩小窗口
            v2 := s[left]
            left++

            if _, ok := need[v2]; ok {
                window[v2]--
                if window[v2] < need[v2] {
                    matchNum--
                }
            }
        }
    }

    return res
}
//leetcode submit region end(Prohibit modification and deletion)
